Optimisasi Konveks: Prinsip-Prinsip Minimisasi Tak Terbatas

Kita beralih dari eksistensi minimum secara teoretis ke mesin algoritmik optimisasi. Tujuan utama kita adalah untuk meminimalkan $f(x)$ (9.1) di mana $f: \mathbf{R}^n \to \mathbf{R}$ adalah konveks dan terdiferensial dua kali secara kontinu. Karena $f$ terdiferensial dan konveks, syarat perlu dan cukup agar titik $x^*$ menjadi optimal adalah $\nabla f(x^*) = 0$.

Rangka Algoritmik

Solusi numerik membangun sebuah urutan minimisasi: Suatu urutan titik-titik $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ dengan $f(x^{(k)}) \to p^*$ saat $k \to \infty$. Setiap langkah memperbarui posisi melalui $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, di mana $\Delta x$ adalah arah penurunan.

Inisialisasi & Konvergensi

Metode-metode yang dijelaskan dalam bab ini membutuhkan titik awal yang sesuai $x^{(0)}$. Titik awal harus berada dalam $\text{dom } f$, dan selain itu himpunan sublevel $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ harus tertutup. Ini menjamin bahwa urutan tetap berada di wilayah yang baik sehingga Hessian memberikan informasi yang berguna.

Arah Penurunan

Arah yang paling sederhana adalah $\Delta x = -\nabla f(x)$. Namun, efisiensi sering kali memerlukan pertimbangan geometri yang berbeda melalui arah penurunan tercuram:

Norm Kuadrat: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
Norm $L_\infty$: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Penurunan Koordinat).

Model Orde Kedua dan Wilayah Kepercayaan

Metode Newton menggunakan aproksimasi Taylor orde kedua: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Persamaan kuadrat ini diminimalkan ketika $v = \Delta x_{nt}$ (langkah Newton). Kita mendefinisikan sebuah wilayah kepercayaan: himpunan $\{v \mid \|v\|_2 \le \gamma\}$. Parameter $\gamma$ mencerminkan tingkat kepercayaan kita terhadap model orde kedua. Ketika model akurat, kita menyelesaikan arahnya melalui $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ dalam sistem KKT.

🎯 Prinsip-Pirnsip Utama Konvergensi

Efisiensi diukur berdasarkan kecepatan hilangnya kesalahan $f(x^{(k)}) - p^*$. Untuk fungsi-fungsi konveks kuat, kesalahan $f(x^{(k)}) - p^*$ akan berkonvergensi menuju nol setidaknya secepat deret geometrik. Dalam konteks metode numerik iteratif, hal ini disebut konvergensi linier.

Batas Suboptimalitas: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, valid jika $\lambda(x) < 1$.
Jumlah Self-Concordance: Jika $f_1, f_2$ adalah self-concordant, maka $f_1 + f_2$ juga self-concordant.
Kepadatan Hessian: Efisiensi diperoleh jika kondisi struktur pita Hessian: $\nabla^2 f(x)_{ij} = 0$ untuk $|i-j| > k$ berlaku.

PERTANYAAN 1

Kondisi mana yang merupakan syarat perlu dan cukup agar x* menjadi minimizer global dari fungsi konveks yang terdiferensial?

$∇² f(x*) ≽ 0$

$∇ f(x*) = 0$

Himpunan sublevel S tertutup

$f(x*) = p^*$

PERTANYAAN 2

Apa yang terjadi pada metode Newton jika kita menerapkan transformasi koordinat (Invariansi Affine)?

Jalur menuju optimum berubah secara signifikan

Algoritma hanya menjadi konvergensi linier

Metode ini tidak tergantung pada transformasi koordinat linier

Hessian menjadi singular

PERTANYAAN 3

Kapan batas suboptimalitas $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$ dijamin valid?

Hanya ketika $\lambda(x) < 1$

Untuk semua $x \in \text{dom } f$

Hanya untuk fungsi kuadrat

Ketika Hessian diagonal

PERTANYAAN 4

Jika $f_1$ dan $f_2$ adalah self-concordant, manakah dari berikut ini juga self-concordant?

$f_1 \cdot f_2$

$f_1 / f_2$

$f_1 + f_2$

$f_1 - f_2$

PERTANYAAN 5

Apa karakteristik kunci dari konvergensi linier dalam metode iteratif?

Kesalahan mencapai nol dalam tepat n langkah

Kesalahan berkonvergensi menuju nol setidaknya secepat deret geometrik

Hessian konstan

Ukuran langkah t selalu 1